CDMA is widely used in cellular and other wireless systems for multiplexing communications among multiple users on a common frequency band. In direct-sequence (DS) CDMA, the transmitter multiplies each user's signal by a distinct code waveform. The code waveforms of the different users have the form of “pseudo-noise” (PN) sequences, also known as spreading codes, and are chosen so as to be as much as possible mutually orthogonal. The receiver receives a composite signal made up of the sum of all of the users' signals, which overlap in time and frequency. To recover the individual signal of a given user, the receiver correlates the composite signal with that user's distinct code.
Multiple access interference (MAI) limits the capacity and performance of DS-CDMA systems. MAI results from the lack of complete orthogonality between the spreading codes, due to random time offsets between the signals of different users, for example. MAI becomes increasingly problematic as the number of interfering users and their power increases, particularly when there are power imbalances among the users. These imbalances typically result from differences in distance between the users and the base station, as well as from fading and other factors that affect signal power. The problems caused by MAI have led a number of groups to develop multi-user detection techniques, in which information about multiple users and their respective code waveforms is used jointly to better detect each individual user. A survey of these techniques is presented by Moshavi in “Multi-User Detection for DS-CDMA Communications,” IEEE Communications Magazine (October, 1996), pages 124–136, which is incorporated herein by reference.
To formulate the multi-user detection problem, we consider a CDMA receiver that receives signals from K users. The received complex-envelope baseband signal x(t) is a superposition of the users' individual signal waveforms, including channel distortion and additive noise n(t):
                              x          ⁡                      (            t            )                          =                                            ∑                              k                =                1                            K                        ⁢                                                            h                  k                                ⁡                                  (                  t                  )                                            *                                                ξ                  k                                ⁡                                  (                  t                  )                                                              +                      n            ⁡                          (              t              )                                                          (        1        )            Here “*” denotes convolution, and hk(t) is the impulse response of the kth user channel (including delay, attenuation, multipath and filtering effects). In the derivation that follows, n(t) is assumed to be Gaussian with mean zero and without correlation between successive noise samples.
The kth user's signal waveform is given by:
                                          ξ            k                    ⁡                      (            t            )                          =                              ∑                          m              =                              -                ∞                                      ∞                    ⁢                                                    b                k                            ⁡                              (                m                )                                      ⁢                                          p                Tb                            ⁡                              (                                  t                  -                                      m                    ⁢                                                                                  ⁢                                          T                      b                                                                      )                                      ⁢                                          c                k                            ⁡                              (                t                )                                                                        (        2        )            In this equation, bk(m) is the mth symbol transmitted by the kth user, wherein bk is selected from a predefined constellation (or alphabet) A. For binary phase shift keying (BPSK), which is the most common modulation scheme in current cellular systems, bk is a bit selected from A={−1,1}. Tb is the symbol duration, and pT(t) is a rectangular pulse with unity value in t ε[0,T) and zero elsewhere. ck(t) is a complex-valued PN spreading waveform, with a chip period Tc=Tb/N, wherein N is the spreading gain of the DS modulation:
                                          c            k                    ⁡                      (            t            )                          =                              ∑                          i              =                              -                ∞                                      ∞                    ⁢                                                    1                                  2                                            ⁡                              [                                                                            γ                      k                                              (                        I                        )                                                              ⁡                                          (                      i                      )                                                        +                                      j                    ⁢                                                                                  ⁢                                                                  γ                        k                                                  (                          Q                          )                                                                    ⁡                                              (                        i                        )                                                                                            ]                                      ⁢                                          p                Tc                            ⁡                              (                                  t                  -                                      i                    ⁢                                                                                  ⁢                                          T                      c                                                                      )                                                                        (        3        )            γk(I)(i) and γk(Q)(i) are independently drawn from {−1,1} with uniform distribution.
The multi-user detection problem can be stated as follows: Let the received signal x(t) be sampled, and assume that the impulse responses hk(t) and the spreading waveforms ck(t) are known. Now estimate the symbols bk(m) from the samples x(t) for all k and m. For the sake of simplicity in framing the problem, it is assumed that the impulse responses of the channels can be expressed as complex scalars hk, that the user signals are mutually synchronized, and that the samples are taken at mid-chip, at a sampling rate equal to the chip rate (i.e., N samples per symbol). It is possible to relax some of these assumptions and still achieve multi-user detection, as described hereinbelow.
The symbols transmitted by the K users at symbol interval m can be written as a K×1 real vector:b(m):=(b1(m), . . . bK(m)T  (4)The samples taken during the mth symbol interval can be arranged as a N×1 complex vector x(m). Rearranging equations (1) and (2) in similar vector form gives the following expression:x(m)=S(m)b(m)+n(m)  (5)Here n(m) is a N×1 complex vector of noise samples. S(m) is a complex N×K matrix, whose kth column is a signature vector sk(m) representing the “symbol signature” of the kth user during the mth symbol interval. The elements of the signature vectors sk(m) are samples of the following waveform:Sk(t; m):=hkck(t), mTb≦t ≦(m+1)Tb   (6)
Given the known elements of x(m) and S(m), in order to solve the multi-user detection problem it is necessary to find the elements of b(m) that best satisfy equation (5). An optimal, maximum-likelihood solution to this problem was framed by Verdu in “Minimum Probability of Error for Asynchronous Gaussian Multiple-Access Channels,” IEEE Transactions on Information Theory 32:1 (January, 1986), pages 85–96, which is incorporated herein by reference. According to this solution, for each m, we find the elements of b within the applicable constellation A ({−1,1} for BPSK, as noted above) that minimize ∥x−Sb∥2. (For brevity, here and below, we write simply b, S and x to represent b(m), S(m) and x(m).) Although optimal, this detector is usually impractical, since it requires an exhaustive search over all possible bεAK.
As a less costly (though suboptimal) alternative, Lupas and Verdu proposed a decorrelating detector in “Linear Multi-User Detectors for Synchronous Code-Division Multiple Access Channels,” IEEE Transactions on Information Theory 35:1 (January, 1989), pages 123–136, which is also incorporated herein by reference. The decorrelating detector finds a vector {tilde over (b)} that minimizes ∥x−Sb∥2 over b εCK, wherein C is the complex plane. The “soft decision” vector {tilde over (b)} is projected onto the constellation AK to arrive at the hard decision output {circumflex over (b)}. For BPSK modulation, the elements {circumflex over (b)}k are given simply by the sign of the real part of the corresponding elements {tilde over (b)}k. Assuming K≦N and full column-rank S, the soft decision solution is given by:{tilde over (b)}=(SHS)−1SHx  (7)wherein SH is the conjugate transpose of S.
The decorrelating detector has been found to provide substantial performance gains over conventional single-user detection, with significantly lower computational complexity than the maximum-likelihood detector proposed previously. It performs well even in the presence of substantial power imbalances among the users. It still entails a substantial computational burden, however, in inverting the matrix SHS.
A number of different solutions have been proposed in order to improve multi-user detection performance. For example, Duel-Hallen suggests combining the decorrelating detector with decision feedback, in “Decorrelating Decision-Feedback Multiuser Detector for Synchronous Code-Division Multiple-Access Channel,” IEEE Transactions on Communications 41:2 (February, 1993), pages 285–290, which is incorporated herein by reference. This detector generates decisions {circumflex over (b)}k iteratively, working down from the stronger user signals to the weaker signals. The decisions made with respect to the stronger users are used in forming decisions for the weaker ones. The decision-feedback detector has been found to outperform the original decorrelating detector as long as the bit-error rate (BER) is not too high, and reliable estimates of the channel gains hk are available.
Various other technique have been suggested in the patent literature for canceling interference among the signals received from multiple CDMA users. For example, U.S. Pat. No. 5,644,592, to Divsalar et al., whose disclosure is incorporated herein by reference, describes a method of parallel interference cancellation, which estimates and subtracts out all of the interference for each user in parallel. U.S. Pat. Nos. 5,363,403, 5,553,062, 5,719,852 and 6,014,373, all to Schilling et al., whose disclosures are also incorporated herein by reference, describe methods for solving the (SHS)−1 matrix using a fast polynomial expansion.